/*
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "bababdccccnnnncccc"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "asdbegrgrtwetcbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class LongestPalindrome {

//    public static String longestPalindrome(String s) {
//        if(s == null || s.length() == 0 || s.length() == 1){
//            return s;
//        }
//        char[] chars = s.toCharArray();
//        String fixed = String.valueOf(chars[0]);
//        boolean isPa;
//        for(int x = 0; x < chars.length; x ++) {
//            for (int i = x + 1; i < chars.length; i++) {
//                if (chars[i] == chars[x]) {
//                    isPa = true;
//                    for (int m = 1; m <= (i - x) / 2; m++) {
//                        if (chars[x + m] != chars[i - m]) {
//                            isPa = false;
//                            break;
//                        }
//                    }
//                    if (isPa) {
//                        int offset = i - x + 1;
//                        if(i - x + 1 > fixed.length()){
//                            fixed = String.valueOf(chars, x, offset);
//                        }
//                    }
//                }
//            }
//        }
//
//        return fixed;
//    }

    public static String longestPalindrome(String s) {
        if(s == null || s.length() == 0 || s.length() == 1){
            return s;
        }
        char[] chars = s.toCharArray();
        int[] max = new int[]{0,0};
        int length = chars.length;
        int maxLen = 1;
        boolean[][] P = new boolean[length][length];
        for(int len = 1; len <= length; len ++) {
            for (int i = 0; i <= length - len; i++) {
                int j = i + len - 1;
                if(len == 1){
                    P[i][j] = true;
                } else if(len == 2){
                    if(chars[i] == chars [j]){
                        P[i][j] = true;
                    } else {
                        P[i][j] = false;
                    }
                } else {
                    P[i][j] = P[i + 1][j - 1] && (chars[i] == chars[j]);
                }
                if(P[i][j] && len > maxLen){
                    max[0] = i;
                    max[1] = j;
                }
            }
        }

        return String.valueOf(chars, max[0], (max[1] - max[0] + 1));
    }


    public String longestPalindromeII(String s){
        if(s == null || s.length() == 0){
            return s;
        }
        char[] chars = s.toCharArray();
        int[] max = new int[]{0,0};
        for(int i = 0; i < chars.length; i++){
            int[] res1 = palindrome(chars, i, i);
            int[] res2 = palindrome(chars, i, i + 1);
            max = getMax(res1, max);
            max = getMax(res2, max);
        }
        return s.substring(max[0], max[1] + 1);
    }

    private int[] getMax(int[] arr1, int[] arr2){
        if(arr1[1] - arr1[0] > arr2[1] - arr2[0]){
            return arr1;
        }
        return arr2;
    }

    private int[] palindrome(char[] chars, int l, int r){
        while(l >= 0 && r < chars.length && chars[l] == chars[r]){
            l --;
            r ++;
        }
        return new int[]{l + 1, r - 1};
    }

    public static void main(String[] args){
        String s = "cbbd";
        System.out.println(new LongestPalindrome().longestPalindromeII(s));
        System.out.println(s.substring(0,1));
    }
}
